//
// Created by Snow on 2023/3/18.
//
#include<cstdio>
#include<cstdlib>
typedef struct SNode
{
    char data;//存放字符
    struct SNode *next;//指向下一个结点的指针
}LinkStrNode;//链串的结点类型
//生成串
void StrAssign(LinkStrNode *&s,char cstr[])
{
    int i;
    LinkStrNode *r,*p;
    s=(LinkStrNode *)malloc(sizeof(LinkStrNode));
    r=s;//r始终指向尾结点
    for(i=0;cstr[i]!='\0';i++)
    {
        p=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        p->data=cstr[i];
        r->next=p;
        r=p;
    }
    r->next=nullptr;//尾结点的next域置为空
}
//销毁串
void DestroyStr(LinkStrNode *&s)
{
    LinkStrNode *pre=s,*p=s->next;
    while(p!=nullptr)
    {
        free(pre);
        pre=p;
        p=p->next;
    }
    free(pre);
}
//串的复制
void StrCopy(LinkStrNode *&s,LinkStrNode *t)
{
    LinkStrNode *p=t->next,*q,*r;
    r=s;//r始终指向尾结点
    while(p!=nullptr)//扫描链串t的所有结点
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p->data;//将p结点复制到q结点
        r->next=q;//将q结点连接到链串s的末尾
        r=q;
        p=p->next;
    }
    r->next=nullptr;//尾结点的next域置为空
}
//判断串相等
bool StrEqual(LinkStrNode *s,LinkStrNode *t)
{
    LinkStrNode *p=s->next,*q=t->next;//p，q分别扫描链串s和t的数据结点
    while(p!=nullptr&&q!=nullptr&&p->data==q->data)
    {
        p=p->next;
        q=q->next;
    }
    if(p==nullptr&&q==nullptr)//s和t的长度相等且对应位置的字符均相同
        return true;
    else
        return false;
}
//求串长
int StrLength(LinkStrNode *s)
{
    int i=0;//i用于累计数据结点的个数
    LinkStrNode *p=s->next;//p指向链串s的首结点
    while(p!=nullptr)//扫描所有的数据结点
    {
        i++;
        p=p->next;
    }
    return i;
}
//串的连接
LinkStrNode *Concat(LinkStrNode *s,LinkStrNode *t)
{
    LinkStrNode *str,*p=s->next,*q,*r;
    str=(LinkStrNode *)malloc(sizeof(LinkStrNode));
    r=str;
    while(p!=nullptr)
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p->data;
        r->next=q;
        r=q;
        p=p->next;
    }
    p=t->next;
    while(p!=nullptr)
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p->data;
        r->next=q;
        r=q;
        p=p->next;
    }
    r->next=nullptr;
    return str;
}
//求子串
//返回顺序串s中从第i(i<=i<=n)个字符开始的由连续j个字符组成的子串
LinkStrNode *SubStr(LinkStrNode *s,int i,int j)
{
    int k;
    LinkStrNode *str,*p=s->next,*q,*r;
    str=(LinkStrNode *)malloc(sizeof(LinkStrNode));
    str->next=nullptr;//置结果串str为空串
    r=str;//r指向结果串尾结点
    if(i<=0||i>StrLength(s)||j<0||j+i-1>StrLength(s))
        return str;//参数不正确时返回空串
    for(k=1;k<i;k++)//让p指向链串s的第i个数据结点
        p=p->next;
    for(k=1;k<=j;k++)//将s的从第i个结点开始的j个结点复制到str
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p->data;
        r->next=q;
        r=q;
        p=p->next;
    }
    r->next=nullptr;
    return str;
}
//子串的插入
//将顺序串s2插入到顺序串s1的第i(1<=i<=n+1)的位置上，并返回产生的结果串
LinkStrNode *InsStr(LinkStrNode *s1,int i,LinkStrNode *s2)
{
    int k;
    LinkStrNode *str,*p1=s1->next,*p2=s2->next,*q,*r;
    str=(LinkStrNode *)malloc(sizeof(LinkStrNode));
    str->next=nullptr;
    r=str;
    if(i<=0||i>StrLength(s1)+1)
        return str;
    for(k=1;k<i;k++)
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p1->data;
        r->next=q;
        r=q;
        p1=p1->next;
    }
    while(p2!=nullptr)
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p2->data;
        r->next=q;
        r=q;
        p2=p2->next;
    }
    while(p1!=nullptr)
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p1->data;
        r->next=q;
        r=q;
        p1=p1->next;
    }
    r->next=nullptr;
    return str;
}
//子串的删除
//在顺序串中删去从第i(1<=i<=n)个字符开始的长度为j的子串
LinkStrNode *DelStr(LinkStrNode *s,int i,int j)
{
    int k;
    LinkStrNode *str,*p=s->next,*q,*r;
    str=(LinkStrNode *)malloc(sizeof(LinkStrNode));
    str->next=nullptr;
    r=str;
    if(i<=0||i>StrLength(s)||j<0||j+i-1>StrLength(s))
        return str;
    for(k=1;k<i;k++)
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p->data;
        r->next=q;
        r=q;
        p=p->next;
    }
    for(k=0;k<j;k++)//让p沿next跳j个结点
        p=p->next;
    while(p!=nullptr)
    {
        q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
        q->data=p->data;
        r->next=q;
        r=q;
        p=p->next;
    }
    r->next=nullptr;
    return str;
}
//子串的替换
//在顺序串s中将第i(1<=i<=n)个字符开始的连续j个字符构成的子串用顺序串t替换
LinkStrNode *RepStr(LinkStrNode *s,int i,int j,LinkStrNode *t)
{
    int k;
    LinkStrNode *str,*p1=s->next,*p2=t->next,*q,*r;
    str=(LinkStrNode*)malloc(sizeof(LinkStrNode));
    str->next=nullptr;
    r=str;
    if(i<=0||i>StrLength(s)||j<0||i+j-1>StrLength(s))
        return str;
    for(k=0;k<i-1;k++)
    {
        q=(LinkStrNode*)malloc(sizeof(LinkStrNode));
        q->data=p1->data;
        r->next=q;
        r=q;
        p1=p1->next;
    }
    for(k=0;k<j;k++)
        p1=p1->next;
    while(p2!=nullptr)
    {
        q=(LinkStrNode*)malloc(sizeof(LinkStrNode));
        q->data=p2->data;
        r->next=q;
        r=q;
        p2=p2->next;
    }
    while(p1!=nullptr)
    {
        q=(LinkStrNode*)malloc(sizeof(LinkStrNode));
        q->data=p1->data;
        r->next=q;
        r=q;
        p1=p1->next;
    }
    r->next=nullptr;
    return str;
}
//输出串
void DispStr(LinkStrNode *s)
{
    LinkStrNode *p = s->next;
    while (p != nullptr)
    {
        printf("%c",p->data);
        p=p->next;
    }
    printf("\n");
}
//设计一个算法，将串s中最先出现的子串“ab”改为“xyz”
void Rep1(LinkStrNode *&s)
{
    LinkStrNode *p=s->next,*q;
    bool find=false;
    while(p!=nullptr&&p->next!=nullptr&&!find)
    {
        if(p->data=='a'&&p->next->data=='b')
        {
            p->data='x';
            p->next->data='z';
            q=(LinkStrNode*)malloc(sizeof(LinkStrNode));
            q->data='y';
            q->next=p->next;
            p->next=q;
            find=true;
        }
        else
            p=p->next;
    }
}
int main()
{
    LinkStrNode *s,*t,*str;
    char str1[]={'a','b','c','\0'};
    char str2[]={'d','e','f','\0'};
    StrAssign(s,str1);
    StrAssign(t,str2);
    DispStr(t);
    str=RepStr(s,2,1,t);
    DispStr(str);
    Rep1(s);
    DispStr(s);
    DestroyStr(s);
    DestroyStr(t);
    DestroyStr(str);
}